<?php
/*
剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。
为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。



示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

难度：简单

https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/


*/

require_once '../class/ListNode.class.php';
$arr = [1,2,3,4,5,6]; $k = 2;
$head = array2LinkList($arr);
$obj = new Code_Offer22();
$res = $obj->main($head, $k);
fetchNode($res);

class Code_Offer22
{
    public function main($head, $k)
    {
        // 快慢指针，快指针先走K步
        $slow = $head;
        $fast = $head;
        for ($i = 0; $i < $k; $i++) {
            $fast = $fast->next;
        }
        // 然后快慢指针一起走。快指针指向尾节点的时候慢指针指向的就是倒数第K个节点
        while ($fast != null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        return $slow;
    }
}